package medium二叉树变链表结构;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution {
    Queue<Integer> queue = new LinkedList<>();
    public void flatten(TreeNode root) {
        if (root == null)
            return;
        if (root.left == null && root.right == null)
            return;
        test(root);                                 //进行递归
        TreeNode node = root;                       //创建node 和 root 同一个地址空间
        while (!queue.isEmpty()){                   //判断是否为空 进行赋值
            node.val = queue.poll();
            if (!queue.isEmpty()){                  //判断是否为空 进入下一个结点
                node.left = null;
                node.right = new TreeNode();
                node = node.right;
            }

        }
    }
    public void test(TreeNode node){       //深度优先遍历把结点的值放到 队列中
        if (node == null)
            return;
        queue.offer(node.val);             //进队列
        test(node.left);
        test(node.right);
    }


    Queue<TreeNode> queue1 = new LinkedList<>();
    public void flatten1(TreeNode root) {
        if (root==null)
            return;
        if (root.left == null && root.right == null)
            return;
        test(root);
        TreeNode node = root;                     //第一个结点为 1
        while (!queue1.isEmpty()){
            node.right = queue1.poll();          //返回的第一个结点 就是 1 然后 1指向本身 就是 本身
            //所有 node.right 这个指针 就是 1这个指针
            node.left = null;
            /*
            if (!queue.isEmpty()){                  //
                node.left = null;
                node.right = new TreeNode();
                node = node.right;
            }
            没进行判空所有多执行了一次 所以是对的
             */
            node = node.right;
        }
    }
    public void test1(TreeNode node){
        if (node == null)
            return;
        queue1.offer(node);
        test(node.left);
        test(node.right);
    }
}
